package airthmetic.exercise.dp;

public class _518_零钱兑换II {

    // 普通动态规划
    public int change(int amount, int[] coins) {
        /**
         因为问题具备重叠子问题和无后效性已经最优子结构。动态规划!
         重叠子问题：选i个硬币凑成amount
         无后效性：选择i个硬币凑成amount不会被后续选择影响
         最优子结构：选择i个硬币凑成amount,是可以被后续问题直接使用

         动态规划思考问题：
         1.确定状态参数和选择
         先思考什么是原问题 什么是子问题
         原问题：选i个硬币凑成amount
         子问题：选择i-1个硬币凑成amount

         状态参数:选择前i个硬币凑成amount，所以是两个状态参数

         选择/决策:不断选择i个硬币和amount

         2.定义dp table的含义
         int[][] dp = new int[i+1][amount+1];
         dp[i][W]表示选择前i个硬币凑成W金额最多有集中组合

         3.初始化dp table
         当硬币为0个时，背包容量不管多大都是无法装满。所以都是0
         当背包容量为0时，硬币不管有几个都有一种办法装满。就是不装。所以都是1

         4.推导状态转移公式
         if(nums[i-1] > w){
         dp[i][w] = dp[i-1][w];
         }else{
         dp[i][w] = dp[i][w-nums[i-1]] + dp[i-1][w];
         }
         */
        int N = coins.length;
        int[][] dp = new int[N+1][amount+1];
        for(int j=0; j<amount+1; j++){
            dp[0][j] = 0;
        }

        for(int i=0; i<N+1; i++){
            dp[i][0] = 1;
        }

        for(int i=1; i<N+1; i++){
            for(int w=1; w<amount+1; w++){
                if(coins[i-1] > w){ // 如果当前硬币面额大于要凑成的金额
                    dp[i][w] = dp[i-1][w];
                }else{
                    dp[i][w] = dp[i][w-coins[i-1]] + dp[i-1][w];
                }
            }
        }
        return dp[N][amount];
    }


    // 状态压缩动态规划
    // 根据结果我们发现求解dp[i][w] 只需要用到dp[i-1][w] 和 dp[i][w-coins[i-1]]
    // 所以我们把dp table 压缩成一维
    public int change2(int amount, int[] coins) {
        /**
         因为问题具备重叠子问题和无后效性已经最优子结构。动态规划!
         重叠子问题：选i个硬币凑成amount
         无后效性：选择i个硬币凑成amount不会被后续选择影响
         最优子结构：选择i个硬币凑成amount,是可以被后续问题直接使用

         动态规划思考问题：
         1.确定状态参数和选择
         先思考什么是原问题 什么是子问题
         原问题：选i个硬币凑成amount
         子问题：选择i-1个硬币凑成amount

         状态参数:选择前i个硬币凑成amount，所以是两个状态参数

         选择/决策:不断选择i个硬币和amount

         2.定义dp table的含义
         int[][] dp = new int[i+1][amount+1];
         dp[i][W]表示选择前i个硬币凑成W金额最多有集中组合

         3.初始化dp table
         当硬币为0个时，背包容量不管多大都是无法装满。所以都是0
         当背包容量为0时，硬币不管有几个都有一种办法装满。就是不装。所以都是1

         4.推导状态转移公式
         if(nums[i-1] > w){
         dp[i][w] = dp[i-1][w];
         }else{
         dp[i][w] = dp[i][w-nums[i-1]] + dp[i-1][w];
         }
         */
        int N = coins.length;
        int[] dp = new int[amount+1];
        dp[0]=1;

        for(int i=1; i<N+1; i++){
            for(int w=1; w<amount+1; w++){
                // if(coins[i-1] > w){ // 如果当前硬币面额大于要凑成的金额
                //     dp[i][w] = dp[i-1][w];
                // }else{
                //     dp[i][w] = dp[i][w-coins[i-1]] + dp[i-1][w];
                // }


                if(coins[i-1] <= w){ // 如果当前硬币面额大于要凑成的金额
                    dp[w] = dp[w-coins[i-1]] + dp[w];
                }
            }
        }
        return dp[amount];
    }

    // 状态压缩
    public int change3(int amount, int[] coins) {
        int N = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 1;

        for(int i=1; i<=N; i++){
            for(int w=1; w<=amount; w++){
                if(coins[i-1] <= w){
                    dp[w] = dp[w] + dp[w - coins[i-1]];
                }
            }
        }

        return dp[amount];
    }
}
